package leetcode.day_2020_11_23_11_29;

/**
 * 1143. 最长公共子序列
 */
public class L_1143 {
    public static void main(String[] args) {
        String text1 = "abcde";
        String text2 = "ace";
        System.out.println(longestCommonSubsequence(text1, text2));
    }

    public static int longestCommonSubsequence(String text1, String text2) {
        int text1L = text1.length();
        int text2L = text2.length();
        int[][] dp = new int[text1L+1][text2L+1];
        // 初始化边界
        for(int i=0; i<=text1L; i++) {
            dp[i][0] = 0;
        }
        for(int j=0; j<=text2L; j++) {
            dp[0][j] = 0;
        }

        for(int i=1; i<=text1L; i++){
            for(int j=1; j<=text2L; j++) {
                if(text1.charAt(i-1) == text2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[text1L][text2L];
    }
}
